package lianbiao;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Stringzhua
 * @Date 2025/10/23 15:18
 * description:双链表
 */
public class DoublyLinkedList {
    // 节点内部类
    static class Node {
        int data;   // 节点存储的数据
        Node next;  // 指向下一个节点的引用
        Node prev;  // 指向前一个节点的引用

        // 节点构造方法
        public Node(int data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    private Node head;  // 链表头节点
    private Node tail;  // 链表尾节点

    // 双向链表构造方法
    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    /**
     * 遍历链表（从头到尾）
     * @return 存储节点数据的List
     */
    public List<Integer> traverseForward() {
        List<Integer> elements = new ArrayList<>();
        Node current = head;
        while (current != null) {
            elements.add(current.data);
            current = current.next;
        }
        return elements;
    }

    /**
     * 遍历链表（从尾到头）
     * @return 存储节点数据的List
     */
    public List<Integer> traverseBackward() {
        List<Integer> elements = new ArrayList<>();
        Node current = tail;
        while (current != null) {
            elements.add(current.data);
            current = current.prev;
        }
        return elements;
    }

    /**
     * 在链表末尾插入节点
     * @param data 插入的节点数据
     */
    public void append(int data) {
        Node newNode = new Node(data);

        // 如果链表为空
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }

        // 将新节点链接到尾部
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }

    /**
     * 在链表头部插入节点
     * @param data 插入的节点数据
     */
    public void prepend(int data) {
        Node newNode = new Node(data);

        // 如果链表为空
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }

        // 将新节点链接到头部
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }

    /**
     * 在指定数据的节点前插入新节点
     * @param targetData 目标节点的数据
     * @param data 新节点的数据
     * @return 插入成功返回true，失败返回false
     */
    public boolean insertBefore(int targetData, int data) {
        // 如果链表为空
        if (head == null) {
            return false;
        }

        // 如果目标是头节点
        if (head.data == targetData) {
            prepend(data);
            return true;
        }

        Node current = head;
        // 查找目标节点
        while (current != null && current.data != targetData) {
            current = current.next;
        }

        // 如果没有找到目标节点
        if (current == null) {
            return false;
        }

        // 创建新节点并插入
        Node newNode = new Node(data);
        newNode.next = current;
        newNode.prev = current.prev;
        current.prev.next = newNode;
        current.prev = newNode;

        return true;
    }

    /**
     * 删除头节点
     * @return 删除成功返回true，失败返回false
     */
    public boolean deleteHead() {
        // 如果链表为空
        if (head == null) {
            return false;
        }

        // 更新头节点
        head = head.next;

        // 如果链表不为空，断开新头节点与旧头节点的连接
        if (head != null) {
            head.prev = null;
        } 
        // 如果链表变为空，同步更新尾节点
        else {
            tail = null;
        }

        return true;
    }

    /**
     * 删除尾节点
     * @return 删除成功返回true，失败返回false
     */
    public boolean deleteTail() {
        // 如果链表为空
        if (tail == null) {
            return false;
        }

        // 更新尾节点
        tail = tail.prev;

        // 如果链表不为空，断开新尾节点与旧尾节点的连接
        if (tail != null) {
            tail.next = null;
        } 
        // 如果链表变为空，同步更新头节点
        else {
            head = null;
        }

        return true;
    }

    /**
     * 删除指定数据的节点
     * @param data 要删除节点的数据
     * @return 删除成功返回true，失败返回false
     */
    public boolean deleteNode(int data) {
        // 如果链表为空
        if (head == null) {
            return false;
        }

        // 如果要删除头节点
        if (head.data == data) {
            return deleteHead();
        }

        // 如果要删除尾节点
        if (tail.data == data) {
            return deleteTail();
        }

        // 查找要删除的节点
        Node current = head;
        while (current != null && current.data != data) {
            current = current.next;
        }

        // 如果没有找到要删除的节点
        if (current == null) {
            return false;
        }

        // 删除中间节点（跳过当前节点）
        current.prev.next = current.next;
        current.next.prev = current.prev;

        return true;
    }

    /**
     * 从头开始搜索指定数据的节点
     * @param data 要搜索的数据
     * @return 存在返回true，不存在返回false
     */
    public boolean search(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    /**
     * 从尾开始搜索指定数据的节点
     * @param data 要搜索的数据
     * @return 存在返回true，不存在返回false
     */
    public boolean searchFromTail(int data) {
        Node current = tail;
        while (current != null) {
            if (current.data == data) {
                return true;
            }
            current = current.prev;
        }
        return false;
    }

    /**
     * 优化搜索（从两端同时向中间搜索）
     * @param data 要搜索的数据
     * @return 存在返回true，不存在返回false
     */
    public boolean optimizedSearch(int data) {
        if (head == null) {
            return false;
        }

        Node headPointer = head;
        Node tailPointer = tail;

        // 两端指针未相遇/未交错时继续搜索
        while (headPointer != tailPointer && headPointer.prev != tailPointer) {
            // 检查头指针指向的节点
            if (headPointer.data == data) {
                return true;
            }
            // 检查尾指针指向的节点
            if (tailPointer.data == data) {
                return true;
            }
            // 移动指针
            headPointer = headPointer.next;
            tailPointer = tailPointer.prev;

            // 指针为空则终止（避免异常）
            if (headPointer == null || tailPointer == null) {
                break;
            }
        }

        // 检查最后一次指针相遇时的节点
        if (headPointer != null && headPointer.data == data) {
            return true;
        }

        return false;
    }

    /**
     * 更新指定旧数据的节点为新数据
     * @param oldData 旧数据
     * @param newData 新数据
     * @return 更新成功返回true，失败返回false
     */
    public boolean updateNode(int oldData, int newData) {
        Node current = head;
        while (current != null) {
            if (current.data == oldData) {
                current.data = newData;
                return true;
            }
            current = current.next;
        }
        // 未找到目标节点
        return false;
    }

    /**
     * 打印链表（格式：data <-> data <-> ...）
     */
    public void printList() {
        List<String> elements = new ArrayList<>();
        Node current = head;
        while (current != null) {
            elements.add(String.valueOf(current.data));
            current = current.next;
        }
        System.out.println(String.join(" <-> ", elements));
    }

    // 主方法：测试双向链表的所有功能
    public static void main(String[] args) {
        // 1. 创建双向链表实例
        DoublyLinkedList dll = new DoublyLinkedList();

        // 2. 向链表末尾插入元素
        dll.append(10);
        dll.append(20);
        dll.append(30);
        System.out.println("插入末尾后：");
        dll.printList();  // 输出: 10 <-> 20 <-> 30

        // 3. 向链表头部插入元素
        dll.prepend(5);
        System.out.println("插入头部后：");
        dll.printList();  // 输出: 5 <-> 10 <-> 20 <-> 30

        // 4. 在指定节点前插入元素
        dll.insertBefore(20, 15);
        System.out.println("在20前插入15后：");
        dll.printList();  // 输出: 5 <-> 10 <-> 15 <-> 20 <-> 30

        // 5. 删除头节点
        dll.deleteHead();
        System.out.println("删除头节点后：");
        dll.printList();  // 输出: 10 <-> 15 <-> 20 <-> 30

        // 6. 删除尾节点
        dll.deleteTail();
        System.out.println("删除尾节点后：");
        dll.printList();  // 输出: 10 <-> 15 <-> 20

        // 7. 删除中间节点
        dll.deleteNode(15);
        System.out.println("删除15后：");
        dll.printList();  // 输出: 10 <-> 20

        // 8. 更新节点数据
        dll.updateNode(20, 25);
        System.out.println("更新20为25后：");
        dll.printList();  // 输出: 10 <-> 25

        // 9. 搜索元素（从头开始）
        System.out.println("搜索10是否存在: " + dll.search(10));    // 输出: true
        System.out.println("搜索25是否存在: " + dll.search(25));    // 输出: true
        System.out.println("搜索15是否存在: " + dll.search(15));    // 输出: false

        // 10. 从尾部开始搜索
        System.out.println("从尾部搜索25是否存在: " + dll.searchFromTail(25));  // 输出: true

        // 11. 优化搜索（双向同时搜索）
        System.out.println("优化搜索10是否存在: " + dll.optimizedSearch(10));  // 输出: true
        System.out.println("优化搜索30是否存在: " + dll.optimizedSearch(30));  // 输出: false

        // 12. 反向遍历链表
        System.out.println("反向遍历链表: " + dll.traverseBackward());  // 输出: [25, 10]

        // 13. 测试插入到不存在的节点前
        boolean success = dll.insertBefore(99, 100);
        System.out.println("尝试插入到不存在的节点99前: " + (success ? "成功" : "失败"));  // 输出: 失败
    }
}